Espaço Logarítmico Randomizado (RL), às vezes chamado de RLP (Espaço Logarítmico Randomizado de tempo Polinomial), é a classe de complexidade de problemas da teoria da complexidade computacional solúveis em espaço logarítmico e tempo polinomial com máquinas de Turing probabilísticas com erro unilateral. É denominado analogamente a RP, que é semelhante, mas não tem restrição logarítmica de espaço.

As máquinas de Turing probabilísticas na definição de RL nunca aceitam incorretamente, mas são permitidas de rejeitar incorretamente menos de 1/3 das vezes; isso é chamado de erro unilateral. A constante 1/3 é arbitrária; qualquer x , com 0 < x < 1 seria o suficiente. Este erro pode reduzido 2^−p(x) vezes para qualquer polinômio p(x) sem utilizar mais do que um tempo polinomial ou espaço logarítmico ao se executar o algoritmo várias vezes.

Às vezes, o nome RL é reservado para a classe de problemas solúveis por máquinas probabilísticas de espaço logarítmico em tempo infinito. No entanto, esta classe pode ser demonstrada como sendo igual a NL utilizando um contador probabilístico, e por isso é geralmente referida como NL em vez disso, o que também mostra que RL está contida em NL. RL está contida em BPL, que é semelhante, mas permite erro bilateral (aceitações incorretas). RL contém L, problemas solúveis por máquinas de Turing determinísticas em espaço logarítmico, já que sua definição é apenas mais geral.

Noam Nisan mostrou, em 1992, o resultado fraco de derandomização fraca de que RL está contida em SC, a classe de problemas solúveis em tempo polinomial e espaço polilogarítmico numa máquina de Turing determinística; em outras palavras, dado um espaço polilogarítmico, um máquina determinística pode simular algoritmos probabilísticos em espaço logarítmico.

Acredita-se que RL é igual a L, isto é, que computação de tempo polinomial logspace (espaço logarítmico) pode ser completamente desrandomizada (não-aleatória); as principais evidências para isso foram apresentadas por Reingold et al. no ano de 2005. Uma prova disso é o santo graal dos esforços no campo de desrandomização incondicional de classes de complexidade. Um passo importante foi a prova de Omer Reingold de que SL é igual a L.